// 同余定理：如果两个整数m、n满足n-m能被k整除，那么n和m对k同余
// 即 ( pre(j) - pre (i) ) % k == 0 则 pre(j) % k == pre(i) % k

typedef struct {
    int key;        // 前辍和取余
    int idx;
    UT_hash_handle hh;
} uthash_t;

void hash_put(uthash_t *hash, int key, int idx) {
    uthash_t *ret = malloc(sizeof(*ret));
    ret->key = key;
    ret->idx = idx;
    HASH_ADD_INT(hash, key, ret);
}


bool checkSubarraySum(int* nums, int numsSize, int k){
    if (numsSize < 2) return false;
    
    // 前辍和保存到原数组
    for (int i = 1; i < numsSize; i++) {
        nums[i] += nums[i-1];
        // nums[0] ~ nums[i]和为k的倍数，或有连续两个0
        if (nums[i] % k == 0 || \
            (i>1 && (nums[i] - nums[i-2] == 0)))
            return true;
    }

    uthash_t *hash = NULL;
    // 通过同余定理，将问题转换化为 找到两个余数相同的前辍和
    for (int i = 0; i < numsSize; i++) {
        uthash_t *ret = NULL;
        int target = nums[i] % k;
        HASH_FIND_INT(hash, &target, ret);

        // 哈希表中是否有相同余数
        if (ret == NULL) {
            ret = malloc(sizeof(*ret));
            ret->key = target;
            ret->idx = i;
            HASH_ADD_INT(hash, key, ret);
            // hash_put(hash, target, i);    // 为啥有问题？
        } else {
            if (i - ret->idx > 1) return true;                
        }
    }
    uthash_t *del, *s;
    HASH_ITER(hh, hash, del, s) {
        HASH_DEL(hash, del);
        free(del);
    }

    return false;
}